package cnki.kg.algorithm;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

public class LRUDemo {
    @Test
    public void test() {
        LURCache2 lruCache=new LURCache2<>(4);
        lruCache.add(1,"a");
        lruCache.add(2,"b");
        lruCache.add(3,"c");
        lruCache.add(4,"d");
        System.out.println("节点列表："+lruCache.toString());
        lruCache.get(3);
        System.out.println("获取节点后："+lruCache.toString());
        lruCache.add(5,"e");
        System.out.println("添加节点后："+lruCache.toString());
        lruCache.remove(2);
        System.out.println("移除节点后："+lruCache.toString());


    }

    public class Node<K, V> {
        public K key;
        public V val;
        public Node<K, V> prev;
        public Node<K, V> next;

        public Node() {

        }

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }

    public class DoubleLinkList<K, V> {
        public Node<K, V> head;
        public Node<K, V> tail;

        public DoubleLinkList() {
            this.head = new Node<>();
            this.tail = new Node<>();
            this.head.next =this.tail;
            this.head.next.prev=this.head;
        }

        public Node<K,V> addHead(Node<K,V> newNode){
            if(newNode==null) return null;
            newNode.prev=this.head;
            newNode.next=this.head.next;//新节点的下一个节点为 旧头节点的next,即尾结点

            this.head.next.prev=newNode;//旧尾结点的前一个节点为新节点
            this.head.next=newNode;//旧头结点的下一个节点是新节点
            return newNode;
        }
        public void removeNode(Node<K,V> node){
            if(node==null) return;
            node.prev.next=node.next;
            node.next.prev=node.prev;
            node.next=null;
            node.prev=null;

        }
        public Node<K,V> getLastNode(){
            return  this.tail.prev;
        }
        public String toString(){
            String res="";
            Node node = head.next;
            while (node!=null&&node.next!=null){
                res+=String.format("{%s:%s}",node.key,node.val);
                node=node.next;
            }
            return res;
        }
    }

    public class LURCache2<K, V> {
        public int maxSize;
        public Map<K,Node<K,V>> mp;
        public DoubleLinkList<K,V> list;

        public LURCache2(int maxSize) {
            this.maxSize = maxSize;
            this.mp =new HashMap<>();
            this.list=new DoubleLinkList<>();
        }
        public Node<K, V>  get(K key){
            Node<K, V> oldNode = mp.get(key);
            if(oldNode==null) return null;
            list.removeNode(oldNode);
            list.addHead(oldNode);
            return oldNode;
        }
        public void  add(K key, V val){
            if(mp.containsKey(key)){
                Node<K, V> oldNode = mp.get(key);
                oldNode.val=val;
                mp.put(key,oldNode);
                list.removeNode(oldNode);
                list.addHead(oldNode);
            }
            else{
                if(mp.size()==maxSize){
                    Node<K, V> lastNode = list.getLastNode();
                    this.mp.remove(lastNode.key);
                    list.removeNode(lastNode);
                }
                Node<K, V> newNode = new Node<>(key, val);
                this.mp.put(key,newNode);
                list.addHead(newNode);
            }


        }
        public void  remove( K key){
            Node<K, V> oldNode = mp.get(key);
            list.removeNode(oldNode);
        }
        public String  toString(){
            return list.toString();
        }
    }
}
